1. Field of the Invention
The present invention relates to network protocols and network intermediate devices executing such protocols; and more particularly to algorithms for managing a tree of network devices for a data network according to a spanning tree protocol.
2. Description of Related Art
Local area networks LANs specified according to IEEE Standards for Local and Metropolitan Area Networks under section 802.x, of all types may be connected together with media access control MAC bridges. Bridges interconnect LAN segments so that stations connected to the LANs operate for many purposes as if they were attached to a single LAN. The MAC bridge according to the IEEE standards is specified for operating below the MAC service boundary, and is transparent to protocols operating above this boundary, including protocols operating in the logical link control sublayer or the network layer. Thus, a bridged local area network provides for interconnection of stations attached to LAN segments of different MAC types, for increases in the physical extent, the number of permissible attachments and the total performance of a LAN, and for the partitioning of a physical LAN support for administrative or maintenance reasons. The MAC bridge is specified according to the IEEE Standard 802.1D (IEEE Std 802.1D-1990, IEEE Standards for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges.) The 802.1D specification is incorporated by reference as if fully set forth herein.
When a bridged network is established, it is possible to create loops in the network caused by providing more than one path through bridges in LAN segments between two points. Thus, according to the 802.1D standard, an active topology for the bridge network is maintained according to the spanning tree protocol which is described in the standard. The spanning tree protocol automatically establishes fully connected (spanning) and loop-free (tree) bridged network topology. It uses a distributed algorithm that selects a root bridge and the shortest path to that root from each LAN. Tie breakers are used to ensure that there is a unique shortest path to the root, while uniqueness of the root is guaranteed by using one of its MAC addresses as part of a priority identifier.
Every LAN in the network has one and only one xe2x80x9cdesignated portxe2x80x9d providing that LAN""s shortest path to the root, through the bridge of which the designated port is a part. The bridge is known as the designated bridge for that LAN. Bridges other than the root bridge at the root of the network can be termed branch bridges. Every branch bridge has a xe2x80x9croot portxe2x80x9d which is the port providing that bridge""s shortest path to the root, across a LAN and through the designated port on a designated bridge. Ports other than the root port are designated ports, or alternate ports according to the standard. An alternate port is connected to a LAN for which another bridge is the designated bridge, and is placed in a blocking state so that frames are not forwarded through that port.
The connectivity through any bridge is thus through its root port to a designated port on another bridge, for connection to devices between the bridge and the root of the spanning tree and from the root to other branches of the spanning tree. For connection to devices between the bridge and leaves of the spanning tree, traffic flows through designated ports on the bridge. When spanning tree information has been completely distributed and is stable, this connectivity will connect all of the LANs in a loop free tree.
According to the spanning tree protocol of the standard, each port on a bridge can assume a blocking state in which frames are not forwarded through the port, or a forwarding state in which frames are forwarded through the port. For a transition from the blocking state to the forwarding state, the protocol requires the port to proceed through transitional states referred to as the listening state and the learning state. In the listening state, the port is preparing to participate in frame relay, however frame relay is temporarily disabled to prevent temporary loops. In the listening state, the port monitors information related to the topology in the network for an interval referred to as the forward delay timer. If no information is received which causes a change in state of the port before expiry of the forward delay timer, then the port transitions to the learning state.
In the learning state, the port continues to prepare for participation in frame relay. The relay is temporarily disabled to prevent loops. In this state, in addition to monitoring bridge protocol data units and other information related to operation of the spanning tree algorithm, the port learns information about end stations that are accessible through the port for use in the forwarding of frames once the port enters the forwarding state. Upon expiration of the forward delay timer, if no better information about the protocol is received, then the port assumes the forwarding state. Thus, the transition from a blocking state to the forwarding state takes at least two times the forward delay timer interval. From the time of detection of a change in topology causing a transition from the blocking to the forwarding state, until the time in which the forwarding state is assumed can be a significant amount of time, as much as 30 seconds in some cases.
In a network of bridges which have a topology managed according to the spanning tree protocol, whenever a bridge detects a change in topology, such as for example when an active link fails, the bridge notifies the root of the active topology with a bridge protocol data unit BPDU packet. The protocol entity at the root of the topology then communicates the change to all of the bridges in the tree. Upon receiving such a notification, the bridges time-out their forwarding databases on all ports, recreate the topology and relearn the MAC addresses for the forwarding databases.
The spanning tree protocol uses a distributed algorithm to select a root bridge and the shortest path to the selected root for each LAN. Tie breakers are used to ensure that there is a unique shortest path and a unique root. The topology is maintained by periodic configuration messages known as Bridge Protocol Data Units BPDUs issued by the root, and distributed to all bridges in the tree. There are two types according to the standard known as Configuration BPDUs and Topology Change BPDUs. The information in a Configuration BPDU is accepted and used by a bridge if it carries better information than already received by the bridge on that port, and propagates the BPDU if it carries better information than already received by the bridge on any of the ports on the bridge. Better information received by a bridge port replaces that previously recorded for the port, and is propagated further if it is the best that the bridge has recorded for any port. Information that is better, is defined by the standard, and includes information from a higher priority root, or from the current root along a lower cost path, or simply more recent information from the current root at the current path cost. All information has a maximum age so current information will be forgotten eventually, if the root or a bridge or link on the shortest path to the root fails. Periodic message transmissions by the root and potential roots together with information aging ensures that the spanning tree maintains full loop-free connectivity even as bridges and links fail, or are added and removed from the network.
The maximum age of spanning tree information can be managed precisely to accommodate worst case message propagation delays, lost messages, the maximum number of bridges between the root and any LAN in the network, and the estimated adjustments in such bridges to the message age. However, in most cases generous worst case xe2x80x9cout of the boxxe2x80x9d defaults are used. Either way the operation of a protocol has the effect that good news, indicating the availability of a better root or link to the root travels quickly while bad news indicating failure of a link or bridge travels slowly.
Unfortunately bridge or link failure is always bad news. To initiate reconfiguration, a bridge ages out current information while receiving no better message. A bridge close to the root uses the same maximum information age as one at the network edge, so the detection time is set by worst case propagation times or defaults. Even if a bridge were to use local link specific failure detection, other bridges will discard this bad news until they have aged out the original better information.
Accordingly, it is desirable to provide a technique for improving the propagation of information about topology changes in bridges operating according to the spanning tree protocol.
The present invention provides modifications to the spanning tree algorithm that allows bad news to propagate quickly. Specifically, protocol entities on bridges process inferior information sent by the designated bridge for each LAN. In addition, bridges use per port hello timers to stimulate information propagation, setting each to suit local link characteristics. This enables early link failure detection.
According to the present invention, if protocol entities in a network implement these changes, the maximum age parameter no longer controls reconfiguration delays. Further, forward delays can be substantially reduced since the delay in transitioning a bridge port from forwarding to blocking is set by the worst case information propagation time. Furthermore, the present invention includes an embodiment in which there are no changes to the format of bridge protocol data units (BPDUs) as specified in the IEEE Standard 802.1D, there are no additional protocol data units required, and the algorithm for computing the topology of the network remains unchanged.
In addition, techniques are provided for expiring information and recomputing the spanning tree upon detection of link failure, upon receipt of a message having a message age greater than its accompanying maximum age, or if the port hello time algorithm times out. In addition to the rules for expiring information, new rules for propagating information are provided allowing rapid propagation of changes. Finally, techniques for burning out information in a configuration message are adopted to ensure that information propagating in the network according to these rapid propagation rules burns out to prevent creation of a data loop caused by recomputing topologies in response to the old information.
Accordingly, the present invention can be characterized as a network device in a network comprising a plurality of local area network segments. A network device includes a plurality of ports coupled to LAN segments in the network. Topology management resources manage the plurality of ports according to a spanning tree algorithm to set an active topology for the plurality of ports. In one preferred embodiment, the topology management resources are compliant with IEEE standard 802.1D. Network device also includes resources that are responsive to the active topology to forward frames incoming through ports in the plurality of ports, and to block the forwarding of frames incoming through other ports in the plurality of ports. These resources include a forwarding database storing for the ports in the plurality of ports, respective sets of destination addresses known to be accessible by frames outgoing on the respective ports. The topology management resources further include logic that computes parameters for managing the active topology, including identification of a root of the tree, identification of a port in the plurality of ports for a root port role used for a preferred path to the root, identification of one or more ports in the plurality of ports for designated port roles to be used for the preferred paths between the root and respective LAN segments, and identification of one or more ports in the plurality of ports for alternate port roles. The management resources also include logic that computes states of ports in the plurality of ports in response to the parameters of the active topology. The ports in the plurality of ports are placed in states according to the active topology. In particular, ports in the root port role are placed in a forwarding state. Ports in a designated port role are placed in a forwarding state. Ports in an alternate port role are placed in a blocking state.
According to the present invention logic is provided to update the configuration information in response to acceptance of configuration messages, along with logic to accept configuration messages carrying topology information on a particular port when the configuration message is received from a port on another protocol entity identified as the designated port for the particular port. Thus, according to the spanning tree algorithm, configuration messages are accepted even if they carry inferior topology information than that stored for the particular port. Such inferior topology information according to the spanning tree standard comprises a root identifier identifying a protocol entity with an equal or lower priority than stored as the root, or assuming the preceeding is equal having a root path cost equal or higher than that stored for the particular root, or assuming the preceeding is equal having a bridge identifier identifying a bridge having a priority equal to or lower than that stored for a designated bridge for the particular root port.
In addition, logic is included on the network device for expiring and recomputing configuration information for the plurality of ports in response to detection of a failure of the link coupled to the particular port, if the particular port is in the root port role. Also information is expired and configuration information recomputed in response to receiving a configuration message on a particular port having a maximum age parameter and a message age parameter, and in which the message age parameter is at least one of equal to, and greater than, the maximum age parameter if the port is in the root port role. Further, logic is provided on the network device to increment the message age parameter by an amount equal to about 1/X of the maximum age parameter. In this case, the parameter X designates a value twice a maximum number plus one of protocol entities traversed by messages in the network. For example, in preferred implementations, the parameter X is about 16 when the maximum number of protocol entities is 7. Alternatively, the parameter X in another embodiment is about 8.
According to another aspect of the invention, the configuration messages include a time interval parameter that indicates a time interval, such as the hello time. The network devices include a timer for ports in the plurality of ports indicating elapsed time from receiving a configuration message on a particular port. Logic is included to expire and recompute the configuration information in response to the timer indicating that the elapsed time reaches a value equal to a function of the time interval parameter carried by the last received configuration message (such as two times the hello time), when the particular port receiving the configuration messages in the root port role.
According to this aspect of the invention, the network devices include resources to propagate a configuration messages including the time interval parameter on a port in the designated port role periodically within the time interval indicated by the time interval parameter, whether or not the device is the root of the network.
According to yet another aspect of the invention, configuration messages are propagated according to rules depending on port role. Thus, resources propagate a configuration messages in response to a change in the configuration information on ports in the plurality of ports which were in the designated port role prior to the change for use by protocol entities between the port in the designated port role and leaves of the tree prior to the change. Also, resources propagate a configuration message in response to a change in the configuration information caused by a previous configuration message received on a port in a root port role, which is root either before or after the change, on ports which are in the designated port role after the change for use by protocol entities between the port in the root port role, and leaves of the tree after the change. Also, configuration messages are propagated in response to the configuration information on all ports in the plurality of ports, if the device identifies itself as the root of the network after the change.
Accordingly, improvements to the spanning tree algorithm are provided which allow for more rapid propagation of topology changes in the network. In particular, the rules improve over the spanning tree algorithm of the ANSI/IEEE Standard 802.1D spanning tree algorithm and protocol by allowing for accepting inferior information, providing additional rules for expiring information, providing additional rules for propagating information from all bridges in the network including the root, and for burning out information using the message age parameters. Overall a more efficient spanning tree algorithm is provided without changing message formats in the preferred embodiment, and without altering the computation techniques for assuring a spanning tree.
Other aspects and advantages of the present invention can be seen upon review of the drawings, the detailed description and the claims which follow.